#define _CRT_SECURE_NO_WARNINGS 2

#include<stdio.h>
#include<stdlib.h>

void Swap(int* a, int* b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
//down
//void AdjustDown(int* a, int n, int root) { 
//		int left = 2 * root + 1;
//		while (left < n) {
//			if (left + 1 < n && a[left] < a[left + 1]) {
//				Swap(&a[left], &a[left + 1]);
//			}
//			if (a[root] < a[left]) {
//				Swap(&a[root], &a[left]);
//				root = left;
//				left = 2 * root + 1;
//			}
//			else {
//				break;
//			}
//		} 
//}
//
//void HeapSort(int* a, int n) {
//	for (int j = 0; j<n; j++) {
//		int root = (n - 2-j) / 2;
//		for (int i = root; i >= 0; i--) {
//			AdjustDown(a+j, n-j, i);
//		}
//	 }
//	
//}
//up
void AdjustDown(int* a, int n, int root) {
	int parent = root;
	int lchild = parent * 2 + 1;
	while (lchild < n) {
		if (lchild + 1 < n && a[lchild] < a[lchild + 1]) {
			lchild++;
		}
		if (a[parent] < a[lchild]) {
			Swap(&a[parent], &a[lchild]);
			parent = lchild;
			lchild = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}

void  AdjustUp(int* a, int n) {
	int child = n - 1;
	int parent = (child - 1) / 2;
	while (child > 0) {
		if (a[child] > a[parent]) {
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			break;
		}
	}
}

void CreateHeapUp(int* a, int n) {
	for (int i = 1; i < n; i++) {
		AdjustUp(a, i);
	}
}

void CreateHeapDown(int* a, int n) {
	int parent = (n - 2) / 2;
	for (int i = parent; i >= 0; --i) {
		AdjustDown(a, n, i);
	}
}

void HeapSort(int* a, int n) {
	//CreateHeapDown(a, n);
	CreateHeapUp(a, n);
	for (int i = 0; i < n - 1; i++) {
		Swap(&a[0], &a[n - 1 - i]);
		AdjustDown(a, n - i-1, 0);
	}
}

int  main() {
	int arr[] = { 1,2,7,8,4,0,3,12,-1 };
	int len = sizeof(arr) / sizeof(arr[0]); 
	HeapSort(arr, len);
	//CreateHeap(arr, len);
	for (int i = 0; i < len; i++) {
		printf("%d ", arr[i]);
	}
	return 0;
}